Koshevoy sinh ngày 21 tháng 12 [lịch cũ 8 tháng 12] năm 1904 tại Oleksandriia, Kherson trong một gia đình nông dân Ukraina. Sau khi tốt nghiệp tiểu học năm 1919, ông làm thợ xay cùng với cha mình trong một năm rưỡi.[1]

Ông gia nhập Hồng quân ngày 13 tháng 2 năm 1920 [2] và được gửi đến Trung đoàn Cossack Đỏ 2 thuộc Sư đoàn kỵ binh Đỏ 8. Trong Nội chiến Nga, ông đã tham gia chiến đấu trên mặt trận Tây Nam, chống lại quân Bạch vệ Ba Lan và Ukraina ở khu vực Chornyi Ostriv, Lityn, Proskurov, Horodok và Rohatyn, sau đó chống lại quân nổi dậy Ukraina.[3]

Sau khi Nội chiến kết thúc, tháng 8 năm 1922, Koshevoy được gửi đến theo học tại các khóa Kỵ binh Krym. Tốt nghiệp tháng 10 năm 1923, ông được bổ nhiệm làm một chỉ huy một phân đội kỵ binh trong Trung đoàn Kỵ binh Đỏ Cossack 3 thuộc Sư đoàn Kỵ binh Đỏ Cossack 1, đồn trú tại Quân khu Ukraina. Trở thành một kursant (học viên sĩ quan) tại Trường Kỵ binh Ukraina vào tháng 8 năm 1924 và tốt nghiệp tháng 9 năm 1927, ông được bổ nhiệm làm trung đội trưởng, phục vụ trong Trung đoàn Kỵ binh 61 thuộc Lữ đoàn Kỵ binh đặc biệt trong Quân khu Moskva. Tháng 11 năm 1931, Koshevoy phục vụ tại Trường quân sự kết hợp VTsIK với tư cách là một phụ tá chỉ huy phân đội súng máy.[3]

Sau khi tham dự các khóa huấn luyện nâng cao chỉ huy thiết giáp (KUKS) tại Leningrad trong khoảng thời gian từ tháng 3 đến tháng 5 năm 1932, ông trở lại trường, làm một chỉ huy trung đội trong tiểu đoàn cơ giới. Tháng 9 năm đó, Koshevoy là chỉ huy trưởng trường trung đoàn của Trung đoàn 61, thuộc Sư đoàn kỵ binh đặc biệt (được thành lập từ Lữ đoàn kỵ binh đặc biệt). Tháng 10 năm 1935, ông được bổ nhiệm làm trung đoàn trưởng. Koshevoy vào Học viện quân sự Frunze vào tháng 5 năm 1936 và sau khi tốt nghiệp vào tháng 1 năm 1939, được bổ nhiệm làm tham mưu trưởng của Sư đoàn kỵ binh số 15, đóng quân tại Quân khu Zabaikal. Ông được chuyển sang chỉ huy Sư đoàn súng trường 65 vào tháng 2 năm 1940.[3] Koshevoy được phong cấp Đại tá vào ngày 29 tháng 2 khi Hồng quân thông qua hệ thống quân hàm.[2]

Sau chiến tranh, Koshevoy chỉ huy các tập đoàn quân Cận vệ 6, tập đoàn quân 5, tập đoàn quân Cận vệ 11, các Quân khu Siberia và Kiev. Ông trở thành Tổng Tư lệnh của Cụm binh đoàn Liên Xô tại Đức năm 1965. Koshevoy được thăng cấp Nguyên soái Liên Xô năm 1968, nhưng bị cách chức khỏi Bộ Tư lệnh Lực lượng Liên Xô tại Đức vào cuối năm 1969.